1. Field of the Invention
This invention generally relates to cache storage in a multilevel data storage hierarchy and more particularly to management of the available cache storage in a cache system having a plurality of processors for managing the allocation of the cache storage.
2. Description of the Prior Art
The performance of data processing systems has improved dramatically through the years. While new technology has brought performance improvements to all functional areas of data processing systems, the advances in some areas have outpaced the advances in other areas. For example, advancements in the rate at which computer instructions can be executed have far exceeded improvements in the rate at which data can be retrieved from storage devices and supplied to the instruction processor. Thus, applications that are input/output intensive, such as transaction processing systems, have been constrained in their performance enhancements by data retrieval and storage performance.
The relationship between the throughput rate of a data processing system, input/output (I/O) intensity, and data storage technology is discussed in "Storage hierarchies" by E. I. Cohen, et al., IBM Systems Journal, 28 No. 1 (1989). The concept of the storage hierarchy, as discussed in the article, is used here in the discussion of the prior art. In general terms, the storage hierarchy consists of data storage components within a data processing system, ranging from the cache of the central processing unit at the highest level of the hierarchy, to direct access storage devices at the lowest level of the hierarchy. I/O operations are required for access to data stored at the lowest level of the storage hierarchy.
Caching takes place at various levels of the storage hierarchy. An instruction processor cache caches data stored in main memory and main memory essentially caches data stored in secondary storage. A second level cache between an instruction processor cache and the main memory is used in the 2200/900 Series dam processing system from Unisys Corporation. Secondary storage devices, such as disk subsystems, are also available with a cache between the electromechanical storage device and the main memory of data processing system.
The cache at each level of the hierarchy requires management logic to control the allocation of available cache storage. The cache management scheme chosen will impact the performance enhancement sought by caching. Two common cache replacement methods are used to select an entry in cache in which to store data when a cache miss is encountered. The round robin replacement method is simple to implement, however, the cache hit rate may suffer due to its simplicity. On the other hand, selecting the least-recently-used entry in the cache to replace may enhance the hit rate at the expense of operational complexity.
A round robin replacement scheme for a cache store is described in U.S. Pat. No. 4,195,343 to Thomas F. Joyce. The round robin method constitutes a first-in first-out policy for cache replacement. Implementation is simple because the logic need only cycle through the available cache store in selecting a location for replacement. A disadvantage to this method is that it ignores the possibility that once a location is referenced, is it likely to be referenced again. Therefore, it would be desirable not to replace recently referenced locations to avoid reading the data from storage and writing it to the cache store. The least-recently-used method addresses this concern.
U.S. Pat. No. 4,636,946 to Michael H. Hartung and Gerald E. Tayler describes the use of a least-recently-used method for cache replacement in a caching a disk storage apparatus. A list of the cache store locations is maintained and is ordered from least-recently-used to most-recently-used. Generally, when a location in the cache store is to be replaced, the least-recently-used location is selected. The disadvantage to this method is that each time a location in the cache store is referenced, the referenced location must be moved to the most recently used end of the ordered list of cache store locations.
Both Joyce and Hartung describe their respective cache management techniques in terms of a single processor managing allocation of the cache storage. When multiple processors have access to the cache storage and each of the processors may selectively allocate portions of the cache storage, both the conventional round robin and least-recently-used cache replacement techniques-may present processing bottlenecks. An example of a multi-processor cache system is described in the co-pending patent application incorporated by reference herein.
An example bottleneck in a multi-processor cache system is where two or more of the processors compete for access to the global variables or linkages used for allocating portions of cache storage. This competition would arise where the two or more processors have detected a cache miss condition and require allocation of cache storage to satisfy the request. In order to maintain the integrity of the global variables and linkages, only one of the processors can be allowed to update the global variables and linkages. This will result in all but one of the processors having to wait to allocate a portion of cache storage.
It would therefore be desirable to have a method for managing allocation of cache storage where processors competing for allocation of cache storage did not have to wait for one another in allocating storage.